In order to improve the performance of computers having a single central processing unit, computer designers have developed architectures that have many central processing units. Often, the central processing units in such multiprocessing computers are connected to each other and to the computer's main memory over a common bus. However, the number of central processors that can be connected to a common bus is limited by the bandwidth needed to support the central processors and the total bandwidth of the common bus. One approach for reducing the bus bandwidth required by each processor in a multi-processor computer involves placing a cache between each processor and the common bus. A cache is a small, high-speed buffer memory that temporarily holds data and/or instructions from a main memory. Once data is loaded into such a local, or processor associated cache, the processor can access the data in the cache without accessing the common bus. Typically, when a processor obtains data from its cache, less data is transmitted over the limited bandwidth of the common bus.
As a result of, and in addition to reducing common bus bandwidth requirements, the use of a cache shortens the time necessary to access memory, either for data or instruction fetch. The information located in the cache may be accessed in much less time than information located in the main memory. Thus, a processor with a cache needs to spend far less time waiting for instructions and operands to be fetched and/or stored.
A cache is made up of many cache lines of one or more words of data. Each cache line has associated with it an address tag that uniquely identifies the line of main memory from which the cache line is copied. Each time the processor makes a memory reference, an address tag comparison is made to see if a copy of the requested line resides in the cache. If the desired line is not in the cache, a “cache miss” occurs. The memory line is then retrieved from the main memory, stored in the cache as a cache line, and supplied to the processor. In addition to using a cache to retrieve data from main memory, the processor may also write data into the cache instead of directly to the main memory. When the processor desires to write data to the memory, the cache makes an address tag comparison to see if the cache line into which data is to be written resides in the cache. If the cache line exists in the cache and is modified or exclusive, the data is written into the cache line in the cache memory. In many systems a data bit for the cache line is then set. The data bit indicates that data in the cache line has been modified, and thus before the cache line is deleted from the cache, the modified data must be written into main memory. If the cache line into which data is to be written does not exist in the cache memory, the cache/memory line must be fetched into the cache or the data written directly into the main memory.
Modern computer systems also use virtual addressing as a means of sharing physical memory among many different processes. In these computers, local caches use a portion of a virtual address as an index to the local cache (a virtually-indexed cache). This is often done as a performance optimization, allowing cache lookup to start before the virtual address has been converted to a physical address. Such systems may require that the underlying chip-set present a portion of the virtual address to the processor for certain bus transactions. This is because a computing system may allow more than one virtual address to map to the same physical address (a concept called aliasing). In systems with virtually indexed caches, there is often the requirement that all virtual references to the same line must map to the same set.
Other computer systems have buses that only support physical addresses. However, a processor using a virtual address cannot be placed on a physical only bus. Thus some mechanism must be provided to allow translation from a virtual bus to a physical bus.